﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0206_CanPartitionKSubsets : IAlgorithm
    {
        // 698. 划分为k个相等的子集

        /*
        给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

        提示：
            1 <= k <= len(nums) <= 16
            0 < nums[i] < 10000
            每个元素的频率在 [1,4] 范围内
        */

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
        }

        // 算法
        public bool CanPartitionKSubsets(int[] nums, int k)
        {
            int all = nums.Sum();
            if (all % k != 0) return false;
            int per = all / k;
            Array.Sort(nums);
            int n = nums.Length;
            if (nums[n - 1] > per) return false;
            bool[] dp = new bool[1 << n];
            int[] curSum = new int[1 << n];
            dp[0] = true;
            for (int i = 0; i < 1 << n; i++)
            {
                if (!dp[i]) continue;
                for (int j = 0; j < n; j++)
                {
                    if (curSum[i] + nums[j] > per) break;
                    if (((i >> j) & 1) == 0)
                    {
                        int next = i | (1 << j);
                        if (!dp[next])
                        {
                            curSum[next] = (curSum[i] + nums[j]) % per;
                            dp[next] = true;
                        }
                    }
                }
            }
            return dp[(1 << n) - 1];
        }
    }
}
